package array;

/**
 * 长度最小的子数组
 * 问：
 *  给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
 * 示例 1:
 *  输入：s = 7, nums = [2,3,1,2,4,3]
 *  输出：2
 *  解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 思路：滑动窗口
 * 所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
 * 1.找中间连续的，就算被窗口夹的范围
 * 2.找长度最小的连续，那就移动窗口两端，先放大窗口，再缩小窗口（试试找），得到最小的
 * <br>
 * <img src="https://code-thinking.cdn.bcebos.com/gifs/209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.gif" alt="滑动窗口"/>
 * <br>
 * 时空：
 *  时间复杂度：O(n)，实际是2 × n 也就是O(n)
 *  空间复杂度：O(1)
 */
public class MinSubArrayLen {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int result = minSubArrayLen(nums, 7);
        System.out.println("result = " + result);
    }

    private static int minSubArrayLen(int[] nums, int target) {
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;
        while (right < nums.length) {
            sum+=nums[right];
            // 缩小窗口
            while (sum >= target) {
                min = Math.min(min, right - left+1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return min==Integer.MAX_VALUE?0:min;
    }
}
